package one;
import java.util.*;
public class A002 {

    /**
     *  2:字母异位词分组
     * @param args
     */
    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        //groupAnagrams(strs);
    }


    /**
     *  解法二：技巧判断是否为异位词
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        //异位词说明字母数相同，所以可以直接把他们放到一个数组中排序再转换成字符串，
        //                                     就可以直接判断是否相同
        Map<String,List<String>> map = new HashMap<>(); //存储异位词，每一个key就是一种异位词,v对应异位词集合
        for(String s : strs) {
            //1.转成数组排序
            char[] tmp = s.toCharArray();
            Arrays.sort(tmp);
            //2.转回字符串比较
            String str = new String(tmp);
            if( !map.containsKey(str)) {
                //3，第一次存储该异位词
                map.put(str,new ArrayList<>());
            }
            //4.统一在存储异位词
            map.get(str).add(s); // List.add()
        }
        //5.将Value转成List返回
        return new ArrayList<>(map.values());
    }


    /**
     * 解法一：暴力
     * 计数数组判断异位词+双循环
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        List<List<String>> ret = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for(int i=0;i<strs.length;i++) {
            List<String> str = new ArrayList<>();
            int[] hash = new int[26];
            String a = strs[i];
            if(set.contains(a)) continue;
            str.add(a);
            for(int k=0;k<a.length();k++) {
                char ch = a.charAt(k);
                hash[(int)ch-97]++;
            }
            for(int j=i+1;j<strs.length;j++) {
                String b = strs[j];
                int[] tmp = new int[26];
                for(int k=0;k<b.length();k++) {
                    char ch = b.charAt(k);
                    tmp[(int)ch-97]++;
                }
                Boolean bool = true;
                for(int k=0;k<26;k++) {
                    if(hash[k]!= tmp[k]) {
                        bool=false;
                        break;
                    }
                }
                if(bool) {
                    str.add(b);
                    set.add(b);
                }
            }
            ret.add(str);
        }
        return ret;
    }
}
